#include "stdafx.h"

#pragma once

struct Node
{
	int data;
	Node* next;
};

Node* Insert(Node** head, int data)
{
	Node* newNode = new Node;
	newNode->data = data;
	newNode->next = 0;

	if(!*head)
	{
		*head = newNode;
	}
	else if(!(*head)->next)
	{
		(*head)->next = newNode;
	}
	else
	{
		Node* current = (*head)->next;
		while(current->next)
		{
			current = current->next;
		}
		current->next = newNode;
	}

	return newNode;
}

Node* Find(Node* head, int data)
{
	while(head && (head->data != data))
	{
		head = head->next;
	}

	return head;
}

Node* InsertAfter(Node* node, int data)
{
	Node* newNode = new Node;
	newNode->data = data;
	newNode->next = node->next;
	node->next = newNode;
	return newNode;
}

void Remove(Node** head, int data)
{
	if(!*head && (*head)->data == data)
	{
		delete(*head);
		*head = 0;
	}
	else if(!(*head)->next && (*head)->next->data == data)
	{
		delete((*head)->next);
		(*head)->next = 0;
	}
	else
	{
		Node* current = (*head)->next;
		while(current->next)
		{
			if(current->next->data == data)
			{
				Node* deleteNode = current->next;
				current->next = current->next->next;
				delete(deleteNode);
				break;
			}
			current = current->next;
		}
	}
}

void RemoveNth(Node** head, unsigned int n)
{
	Node* curr = *head;

	if(!n)
	{
		*head = (*head)->next;
		delete(curr);
	}
	else
	{
		Node* prev;
		while(curr->next && n)
		{
			prev = curr;
			curr = curr->next;
			n--;
		}

		if(!n)
		{
			prev->next = curr->next;
			delete(curr);
		}
	}
}


void Clear(Node** head)
{
	Node* current = *head;
	while(current)
	{
		(*head) = current->next;
		delete(current);
		current = *head;
	}
}

void ReverseThreePtr(Node** head)
{
	Node *next, *curr = 0, *prev;
	next = *head;
	while(next)
	{
		prev = curr;
		curr = next;
		next = next->next;

		curr->next = prev;
	}
	*head = curr;
}

void ReverseTwoPtr(Node** head)
{
	Node *next, *prev = 0;

	if(!*head)
	{
		return;
	}

	next = (*head)->next;
	(*head)->next = prev;

	while(next)
	{
		prev = (*head);
		(*head) = next;
		next = next->next;

		(*head)->next = prev;
	}
}

Node* ReverseRecursive(Node* head)
{
	if(!head || !head->next)
	{
		return head;
	}
	Node *temp = ReverseRecursive(head->next);
	head->next->next = head;
	head->next = 0;
	return temp;
}

void ReverseAlternative(Node** head)
{
	Node *prev, *curr, *next;

	if(!*head || !(*head)->next)
	{
		return;
	}

	prev = 0;
	curr = *head;
	next = *head = (*head)->next;
	
	while(next)
	{
		prev = curr;
		curr = next;
		next = next->next;

		if(next && next->next)
		{
			curr->next = prev;
			prev->next = next->next;

			prev = curr;
			curr = next;
			next = next->next;
		}
		else
		{
			curr->next = prev;
			prev->next = next;
			break;
		}
	}
}

bool HasCycle(Node* head)
{
	if(!head)
	{
		return false;
	}

	Node *slow = head, *fast = head->next;

	while(slow && fast)
	{
		slow = slow->next;
		if(fast->next && fast->next->next)
		{
			fast = fast->next->next;
		}
		else
		{
			break;
		}

		if(fast == slow || fast->next == slow)
		{
			return true;
		}
	}

	return false;
}

void RemoveCycle(Node* head)
{
	if(!head)
	{
		return;
	}

	Node *slow = head, *fast = head->next, *prev;

	while(slow && fast)
	{
		slow = slow->next;
		if(fast->next && fast->next->next)
		{
			prev = fast->next;
			fast = fast->next->next;
		}
		else
		{
			break;
		}

		if(fast == slow)
		{
			prev->next = 0;
			break;
		}
		else if(fast->next == slow)
		{
			fast->next = 0;
			break;
		}
	}
}

void Print(const Node *head)
{
	using namespace std;

	cout << "LinkedList: ";
	while(head)
	{
		cout << head->data << ", ";
		head = head->next;
	}
	cout << endl;
}

void UseLinkedList()
{
	using namespace std;

	Node* head = 0;
	Insert(&head, 1);
	Insert(&head, 2);
	Insert(&head, 3);
	Insert(&head, 4);
	InsertAfter(Insert(&head, 5), 6);
	Node* found = Find(head, 3);
	if(found)
	{
		cout << "Found: " << found->data << endl;
	}
	Remove(&head, 3);
	found = Find(head, 6);
	if(found)
	{
		cout << "Found: " << found->data << endl;
	}
	Print(head);
	ReverseThreePtr(&head);
	Print(head);
	ReverseTwoPtr(&head);
	Print(head);
	head = ReverseRecursive(head);
	Print(head);
	ReverseAlternative(&head);
	Print(head);
	RemoveNth(&head, 0);
	Print(head);
	RemoveNth(&head, 1);
	Print(head);
	RemoveNth(&head, 2);
	Print(head);
	Clear(&head);
	Insert(&head, 1);
	Insert(&head, 2);
	Insert(&head, 3);
	Insert(&head, 4);
	InsertAfter(Insert(&head, 5), 6);
	cout << "Has cycle: " << HasCycle(head) << endl;
	Node* found1 = Find(head, 6);
	Node* found2 = Find(head, 3);
	found1->next = found2;
	cout << "Has cycle: " << HasCycle(head) << endl;
	RemoveCycle(head);
	cout << "Has cycle: " << HasCycle(head) << endl;
	Clear(&head);
}

